|
Modular exponentiation is a type of exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography. The operation of modular exponentiation calculates the remainder when an integer ''b'' (the base) raised to the ''e''th power (the exponent), ''b''''e'', is divided by a positive integer ''m'' (the modulus). In symbols, given base ''b'', exponent ''e'', and modulus ''m'', the modular exponentiation ''c'' is: ). For example, given , and , the solution is the remainder of dividing 53 = 125 by 13. Given integers ''b'' and ''e'', and a positive integer ''m'', a unique solution ''c'' exists with the property . Modular exponentiation can be performed with a ''negative'' exponent ''e'' by finding the modular multiplicative inverse ''d'' of ''b'' modulo ''m'' using the extended Euclidean algorithm. That is: : where and Modular exponentiation similar to the one described above are considered easy to compute, even when the numbers involved are enormous. On the other hand, computing the discrete logarithm – that is, the task of finding the exponent ''e'' when given ''b'', ''c'', and ''m'' – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms. ==Straightforward method== The most straightforward method of calculating a modular exponent is to calculate ''b''''e'' directly, then to take this number modulo ''m''. Consider trying to compute ''c'', given ''b'' = 4, ''e'' = 13, and ''m'' = 497: : One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer ''c'' is determined to be 445. Note that ''b'' is only one digit in length and that ''e'' is only two digits in length, but the value ''b''''e'' is 8 digits in length. In strong cryptography, ''b'' is often at least 256 binary digits (78 decimal digits). Consider ''b'' = 5 × 1076 and ''e'' = 17, both of which are perfectly reasonable values. In this example, ''b'' is 77 digits in length and ''e'' is 2 digits in length, but the value ''b''''e'' is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably. As ''b'' and ''e'' increase even further to provide better security, the value ''b''''e'' becomes unwieldy. The time required to perform the exponentiation depends on the operating environment and the processor. The method described above requires O(''e'') multiplications to complete. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「modular exponentiation」の詳細全文を読む スポンサード リンク
|